package com.xigua._树;

import com.xigua.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。
 * @date 2022/4/1817:15
 */
public class _面试题04_06_后继者 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5,
                new TreeNode(3,new TreeNode(2,new TreeNode(1),null),new TreeNode(4)),
                new TreeNode(6));
        TreeNode p = new TreeNode(1, null, null);
        inorderSuccessor(treeNode,p);
    }

    static List<Integer> list = new ArrayList<>();
    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root);
        for (int i = 0; i < list.size()-1; i++) {
            if (p.val == list.get(i))return findNode(root,list.get(i+1));
        }
        return null;
    }

    static TreeNode findNode(TreeNode root, Integer value) {
        if (root == null) return null;
        if (root.val == value) return root;
        if (root.val >value){
            return findNode(root.left,value);
        }else {
            return findNode(root.right,value);
        }
    }

    static void dfs(TreeNode root) {
        if (root == null) return ;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }

}
